import java.util.BitSet;
import java.util.Random;

public class Bloom {
    private BitSet bitset; //位图
    private int size;
    private int hashCount;

    public Bloom(int size, int hashCount) {
        this.size = size;
        this.hashCount = hashCount;
        this.bitset = new BitSet(size);
    }

    public void add(String s) {
        int[] hashes = hash(s);
        for (int hash : hashes) {
            bitset.set(hash, true);
        }
    }

    // 多个hash函数（获得多个Hash值）
    // hash 函数必须要是固定的
    private int[] hash(String s) {
        int[] hashes = new int[hashCount];
        for (int i = 0; i < hashCount; i++) {
            int code = s.hashCode();

            hashes[i] = Math.abs(code | code >> i) % size;
        }
        return hashes;
    }

    public boolean contains(String s) {
        int[] hash = hash(s);
        for (int h : hash) {
            if (!bitset.get(h))
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Bloom bloomFilter = new Bloom(1000, 4);
        bloomFilter.add("hello");
        bloomFilter.add("world");

        System.out.println(bloomFilter.contains("hello")); // true
        System.out.println(bloomFilter.contains("world")); // true
        System.out.println(bloomFilter.contains("java"));  // false（可能为false或true，取决于哈希冲突）
    }
}
